package leetcode.primary;

public class T60 {
    int N;
    public String getPermutation(int n, int k) {
        StringBuffer ans = new StringBuffer();
        N=n;
        dfs(ans,n,k,N_Factorial(n),new boolean[n+1]);
        return ans.toString();
    }

    public void dfs(StringBuffer ans,int n,int k,int n_factorial,boolean[] book){
        int n_1factorial = n_factorial/n;
        int quotient = (int)Math.ceil((double) k/n_1factorial);
        int remainder;
        if (k<=n_1factorial){
            remainder = k;
        }else {
            remainder =k-k/n_1factorial*k;
        }
        if (remainder==0 && n>3){
            remainder = k;
        }
        if (n==3 ){
            if (remainder==0){
                remainder = 2;
            }else {
                remainder = 1;
            }
        }
        if (n==2){
            remainder=1;
        }
        int j=0;
        for (int i=1;i<=N;i++){
            if (!book[i]){
                j++;
            }
            if (j==quotient){
                book[i]=true;
                ans.append(String.valueOf(i));
                System.out.println("n="+n+" remainder="+remainder+" "+String.valueOf(i));
                break;
            }
        }

        if (n>1){
            dfs(ans,n-1,remainder,n_1factorial,book);
        }

    }

    public int N_Factorial(int n){
        int sum=1;
        for (int i =1;i<=n;i++){
            sum*=i;
        }
        return sum;
    }

    public static void main(String[] args) {
        T60 test = new T60();
        System.out.println(test.getPermutation(4,12));
    }
}
